#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>

using namespace std;

const int N = 1010;
int n, V, v[N], w[N];

int dp[N][N];

int main()
{
    cin >> n >> V;

    for (int i = 1; i <= n; ++i)
        cin >> v[i] >> w[i];


    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= V; ++j)
        {
            dp[i][j] = dp[i - 1][j];
            if (j >= v[i])
            {
                dp[i][j] = max(dp[i][j], dp[i][j-v[i]] + w[i]);
            }
        }
        /*for (int k = 0; j - k * v[i] >= 0; ++k)
            dp[i][j] = max(dp[i][j], dp[i - 1][j - k * v[i]] + k * w[i]);*/

    cout << dp[n][V] << endl;

    memset(dp, 0, sizeof dp);

    for (int i = 1; i <= V;++i)
        dp[0][i] = -1;

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= V; ++j)
        {
            dp[i][j] = dp[i - 1][j];
            if (j >= v[i] && dp[i][j - v[i]] != -1)
            {
                dp[i][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]);
            }
        }

    dp[n][V] = dp[n][V] == -1 ? 0 : dp[n][V];
    cout << dp[n][V] << endl;

    return 0;
}